Many of today's computing applications require storage of large volumes of data, and the number of such applications is constantly increasing as the use of computers extends to new disciplines. Moreover, the proliferation of computer communication networks is resulting in massive transfer of data over communication links. Reducing costs associated with the storage and communication of data may be obtained through data compression techniques.
A simple characterization of data compression involves transforming or encoding a string of symbols in one representation, such as ASCII, into another string (sometimes called codewords) which may contain the same information as the original string, but whose length is smaller. The aim of data compression is to reduce redundancy in the original string of symbols, and thereby increase effective data density.
A variety of data compression techniques exists today. Such data compression techniques may be categorized as block-block, block-variable, variable-block, or variable-variable. Block-block indicates that the original string of characters and the resulting codewords are of fixed length. Variable-variable data compression techniques encode original strings of symbols of variable-length into variable-length codewords. Huffman coding is one example of a variable-variable data compression technique.
A Huffman encoder typically uses a Huffman statistical model to encode a string of symbols into a series of variable length codewords. The Huffman encoder operates to assign short codewords to symbols in the string that occur most often and longer codewords to the symbols in the string that occur the least often. The construction of Huffman codes is further described in an article by David Huffman, entitled “A Method for the Construction of Minimum Redundancy Codes” in the proceedings of the I. R. E., volume 40, pages 1098–1101, 1952.
While prior art data compression techniques have proven useful, new data compression techniques are always needed in order to reduce storage requirements of computing systems further as well as to improve the speed at which data may be communicated. Thus, it is with respect to these considerations and others that the present invention has been made.